//package cn.edu.xjtu.data_structure.experiment.ex_4;
//
//import cn.edu.xjtu.data_structure.chapter02_stack_queue.queue.MyQueue;
//import cn.edu.xjtu.data_structure.experiment.ex4.Edge;
//import cn.edu.xjtu.data_structure.experiment.ex4.treeNode;
//import cn.edu.xjtu.data_structure.experiment.test.GraphADT;
//
//import java.io.*;
//import java.util.ArrayList;
//import java.util.HashMap;
//import java.util.Queue;
//
//public class SixDegrees {
//
//    private static HashMap name = new HashMap();
//    static ArrayList List = new ArrayList();
//
//    public static treeNode BFS(GraphADT G, int start){
//        MyQueue Q = new MyQueue();
//        G.setMark(start,1);
//        treeNode res = new treeNode(start);
//        Q.enQueue(res);
//        int len = 1;
//        while (!Q.isEmpty()){
//            for (int i = 0; i < len; i++){
//                treeNode father = (treeNode) (Q.deQueue());
//                for (Edge w = G.First((int)(father.getVal())); G.isEdge(w); w=G.next(w))
//                {
//                    if(G.getMark(G.v2(w))==0)
//                    {
//                        G.setMark(G.v2(w),1);
//                        if((G.v2(w))==(int)name.get("Kevin Bacon"))
//                        {
//                            return new treeNode(G.v2(w),father);
//                        }
//                        Q.enQueue(new treeNode(G.v2(w),father));
//                    }
//                }
//            }
//            len = Q.getCurLen();
//        }
//        return null;
//    }
//
//    public static String txtToString(File file) {
//        List.add(" ");
//        StringBuilder result = new StringBuilder();
//        try {
//            BufferedReader br = new BufferedReader(new FileReader(file));
//            String s = null;
//            while ((s = br.readLine()) != null) {
//                result.append(System.lineSeparator() + s +'\n');
//            }
//            br.close();
//        } catch (Exception e) {
//            e.printStackTrace();
//        }
//        return result.toString();
//    }
//
//    public static void TypeIn(GraphADT graph, String path){
//        File fileName = new File(path);
//        String data = txtToString(fileName);
//        StringReader stringin = new StringReader(data);
//        StreamTokenizer st = new StreamTokenizer(new BufferedReader(
//                stringin));
//
//        st.ordinaryChar('/');
//        st.wordChars(' ', ' ');
//        st.wordChars(',', ',');
//        st.wordChars('\'', '\'');
//        st.wordChars('\n', '\n');
//        st.wordChars('(', ')');
//        st.wordChars('0', '9');
//        st.quoteChar('/');
//        st.quoteChar('\n');
//        Queue temp = new Queue();
//        int num = 1;
//
//        while (true){
//            try {
//                if (!(st.nextToken()!=StreamTokenizer.TT_EOF)) break;
//            } catch (IOException e) {
//                e.printStackTrace();
//            }
//
//            switch (st.ttype){
//                case StreamTokenizer.TT_EOL:
//                {
//                    String edge = (String) temp.deQueue();
//                    int len = temp.getCurLen();
//                    String[] names = new String[len];
//                    for (int i = 0; i < len; i++){
//                        names[i] = (String) temp.deQueue();
//                    }
//                    for (int i = 0; i < len; i++){
//                        for (int j = len - 1; j > i; j--){
//                            graph.setEdge((int)name.get(names[i]),(int)name.get(names[j]),(int)name.get(edge));
//                            graph.setEdge((int)name.get(names[j]),(int)name.get(names[i]),(int)name.get(edge));
//                        }
//                    }
//                    break;
//                }
//                default:
//                    temp.enQueue(st.sval);
//                    if(name.containsKey(st.sval))
//                        break;
//                    name.put(st.sval,num);
//                    List.add(st.sval);
//                    num++;
//                    break;
//            }
//        }
//
//    }
//
//    public static void main(String[] args){
//        GraphADT test = new GraphADT(200);
//        TypeIn(test,"C:\\Users\\75509\\Desktop\\数据结构作业\\数据结构第四次作业\\Simple.txt");
//        System.out.println(name.containsKey("Brad Pitt"));
//        treeNode res = BFS(test,(int)name.get("Brad Pitt"));
//        while(true){
//            int a = (int) res.getVal();
//            res = res.getFather();
//            if(res == null)
//                break;
//            int b = (int) res.getVal();
//            System.out.printf("%s -> %s by %s", List.get(a), List.get(b), List.get(test.weight(a, b)));
//            System.out.println();
//        }
//    }
//
//}
//
//
////        Graph test = new Graph(200);
////        test.setEdge(0,1,1);
////        test.setEdge(1,2,2);
////        test.setEdge(5,3,3);
////        test.setEdge(3,4,4);
////        test.setEdge(1,5,5);
////        test.setEdge(4,5,6);
////        test.setEdge(1,0,1);
////        test.setEdge(2,1,2);
////        test.setEdge(3,5,3);
////        test.setEdge(4,3,4);
////        test.setEdge(5,1,5);
////        test.setEdge(5,4,6);
////        treeNode res = BFS(test,4);
////        while(true){
////            int a = (int) res.getVal();
////            res = res.getFather();
////            if(res == null)
////                break;
////            int b = (int) res.getVal();
////            System.out.printf("%d -> %d by %d",a,b,test.weight(a,b));
////            System.out.println();
////        }